//------------------------------------------------------------------------------
//	 HashUtils.hh
//
//------------------------------------------------------------------------------
// $Id: //CBT-depot/CBT++/include/HashUtils.hh#4 $
//------------------------------------------------------------------------------
// $Log:$
//==============================================================================
//.......1.........2.........3.........4.........5.........6.........7.........8
//

#ifndef _HASH_UTILS
#define _HASH_UTILS

#include "LocalSTL.hh"
#include "CLibraryAdditions.hh"
#include "FileUtils.hh"

//-------------------------------------------
// * eqStr
//-------------------------------------------
// Functor to compare two strings for equality.  
//
class eqStr{
 public:
  bool operator()(const string &s1,const string &s2) const {
    if (s1.size()!= s2.size()) return(false);
	 
    register const int ssize = s1.size();
    for(register int i = 0;i< ssize;i++){
      if (s1[i]!=s2[i]) return(false);
    }
    return(true);
  }
};

//-------------------------------------------
// * BasicStringHashF
//-------------------------------------------
// This is a 'hash traits' object to order the sequence it controls. 
// This functor must satisfy the following constraints (STL imposed):
// 
// * operator(string) serves as a hash function which yeilds a distribution of values.
//  
// * for any value k1 that precedes k2 in the sequence and has the same hash value
//   operator(k1,k2) is false.  operator(k1,k2) must impose a strict weak ordering 
//   on the keys.   i.e. the default is less<key>. 
// 
// * bucket_size specifies the mean number of elements per 'bucket' (hash-table entry) 
//   that the container should endeavor not to exceed.  Must be > 0.  Default is 4. 
// 
// * min_buckets specifies the minimum number of buckets to maintain in hash table. 
//   must be power of 2  and > 0.   Default is 8.  
// 
//
class BasicStringHashF {
 public:
  enum
    {
      bucket_size = 4,
      min_buckets = 8
    };
	
  size_t operator()(const string & s) const
  {
    register unsigned long h = 0;
    for(register int i = 0;i< s.size();i++){
      h = 5 * h + s[i];
    }	 
    return((size_t)h);
  }

	// KJD I thought that it expected operator(a,b) to be equal
	// but it turns out it expects it to be less than.   Don't 
	// know where I got the equal idea.  
  bool equal_string(const std::string &s1,const std::string &s2) const {
    if (s1.size()!= s2.size()) {
			return(false);
		}
    register const int ssize = s1.size();
    for(register int i = 0;i< ssize;i++){
      if (s1[i]!=s2[i]) {
				return(false);
			}
    }
    return(true);
  }
	
	bool lt_string(const std::string &s1, const std::string &s2) const{
		return(comp(s1,s2));
	}
	
  bool operator()(const string& s1, const string& s2) const {
    return(lt_string(s1,s2));
  }
	
	std::less<string> comp;
};


//-------------------------------------------
// * StringSet
//-------------------------------------------
// A hash set of strings.  
//
//class StringSet : public hash_set<string,BasicStringHashF,eqStr>{
class StringSet : public hash_set<string,BasicStringHashF>{
 public:

  bool Contains(string key){
    StringSet::iterator it;
    it = find(key);
    if (it != end()) return(true);
    else return(false);
  }

  void Add(string key){
    insert(key);
  }

  void Remove(string key){
    erase(key);
  }

};

//-------------------------------------------
// * IntSet
//-------------------------------------------
// A hash set of integers
//
class IntSet : public hash_set<int,hash<int>,equal_to<int> >{
 public:

  bool Contains(int key){
    IntSet::iterator it;
    it = find(key);
    if (it != end()) return(true);
    else return(false);
  }

  void Add(int key){
    insert(key);
  }

  void Remove(int key){
    erase(key);
  }

};


//------------------------------------------------------------------------------
// * Int2IntMap
//------------------------------------------------------------------------------
// A hash to implement the mapping one set of integers and another set of integers
//
class Int2IntMap : public  hash_map<int,int,hash<int>,equal_to<int> > {
 public:
  bool Contains(int query){
    Int2IntMap::iterator it;
    it = (*this).find(query);
    if (it == (*this).end()) return(false);
    else return(true);
  }
  
  void Add(int key,int value){
    (*this)[key] = value;
  }

  int GetValue(int key){
    if (!Contains(key)){
      return(0);
    }else{
      return((*this)[key]);
    }
  }
};



//------------------------------------------------------------------------------
// * Int2FloatMap
//------------------------------------------------------------------------------
// A hash to implement the mapping one set of integers to a set of floats. 
//
class Int2FloatMap : public  hash_map<int,float,hash<int>,equal_to<int> > {
 public:
  bool Contains(int query){
    Int2FloatMap::iterator it;
    it = (*this).find(query);
    if (it == (*this).end()) return(false);
    else return(true);
  }
  
  void Add(int key,float value){
    (*this)[key] = value;
  }

  float GetValue(int key){
    if (!Contains(key)){
      return(0);
    }else{
      return((*this)[key]);
    }
  }
};



//------------------------------------------------------------------------------
// * Int2IntMultiMap
//------------------------------------------------------------------------------
// A hash to implement the mapping one integer to multiple integers.  
//
class Int2IntMultiMap : public  hash_multimap<int,int,hash<int>,equal_to<int> > {
 public:
  bool Contains(int key){
    Int2IntMultiMap::iterator it;
    pair<Int2IntMultiMap::const_iterator,Int2IntMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return(false);
    else return(true);

  }
  
  void Add(int key,vector<int> &Values){
    for(int i = 0;i< Values.size();i++){
      insert(Int2IntMultiMap::value_type(key,Values[i]));
    }
  }


  void Add(int key,int Value){
    insert(Int2IntMultiMap::value_type(key,Value));
  }

  void GetValues(int key,vector<int> &Values){
    Int2IntMultiMap::const_iterator it;
    pair<Int2IntMultiMap::const_iterator,Int2IntMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return;

    for(it = p.first;it != p.second;it++){
      Values.push_back((*it).second);
    }
  }
 
};


//------------------------------------------------------------------------------
// * String2LongMap
//------------------------------------------------------------------------------
// A hash to implement the mapping between strings and integers. 
//
//
class  String2LongMap : public hash_map<string,long,BasicStringHashF>{
 public:
  bool Contains(string query){
    String2LongMap::iterator it;
    it = (*this).find(query);
    if (it == (*this).end()) return(false);
    else return(true);
  }

  int GetValue(string key){
    if (!Contains(key)){
      return(0);
    }else{
      return((*this)[key]);
    }
  }
  
  void Add(string key,int value){
    (*this)[key] = value;
  }
};


//------------------------------------------------------------------------------
// * String2IntMap
//------------------------------------------------------------------------------
// A hash to implement the mapping between strings and integers. 
//
//
class  String2IntMap : public hash_map<string,int,BasicStringHashF>{
 public:
  bool Contains(string query){
    String2IntMap::iterator it;
    it = (*this).find(query);
    if (it == (*this).end()) return(false);
    else return(true);
  }

  int GetValue(string key){
    if (!Contains(key)){
      return(0);
    }else{
      return((*this)[key]);
    }
  }
  
  void Add(string key,int value){
    (*this)[key] = value;
  }
};


//------------------------------------------------------------------------------
// * String2IntMultiMap
//------------------------------------------------------------------------------
// A hash to implement the mapping of a string to multiple integers. 
//
class String2IntMultiMap : public  hash_multimap<string,int,
						 BasicStringHashF> {
 public:
  bool Contains(string key){
    String2IntMultiMap::iterator it;
    pair<String2IntMultiMap::const_iterator,String2IntMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return(false);
    else return(true);
  }

  // Returns true if the multimap contains the pair (key,targetvalue)
  bool Contains(string key,int targetvalue){
    pair<String2IntMultiMap::const_iterator,String2IntMultiMap::const_iterator> p;
    p = equal_range(key);
    if (p.first == end()) return(false);

    // The key exists, see if any of this key's values are equal to value..
    String2IntMultiMap::const_iterator it;
    for(it = p.first;it != p.second;it++){
      int value = (*it).second;
      if (value  == targetvalue) return(true);
    }
    return(false);
  }
  
  void Add(string key,vector<int> &Values){
    for(int i = 0;i< Values.size();i++){
      insert(String2IntMultiMap::value_type(key,Values[i]));
    }
  }


  void Add(string key,int Value){
    insert(String2IntMultiMap::value_type(key,Value));
  }

  // Walking with an iterator through the multi-map gives you all of the 
  // key-value pairs, but a given key may occurr many times in this list. 
  // This function gives you a non-redundant set of keys. 
  void GetKeys(vector<string> &Keys){
	 
    StringSet S;
    String2IntMultiMap::iterator it;
    for(it = begin();it != end();it++){
      string key = (*it).first;
      S.Add(key);
    }

    StringSet::iterator sit;
    for(sit = S.begin();sit != S.end();sit++){
      Keys.push_back((*sit));
    }
  }


  void GetValues(string &key,vector<int> &Values){
    String2IntMultiMap::const_iterator it;
    pair<String2IntMultiMap::const_iterator,String2IntMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return;

    for(it = p.first;it != p.second;it++){
      Values.push_back((*it).second);
    }
  }
 
};


//------------------------------------------------------------------------------
// * String2StringMap
//------------------------------------------------------------------------------
// A hash to implement the mapping one set of strings to another set of strings
//
class String2StringMap : public  hash_map<string,string,BasicStringHashF> {
 public:
  bool Contains(string query){
    String2StringMap::iterator it;
    it = (*this).find(query);
    if (it == (*this).end()) return(false);
    else return(true);
  }
  
  void Add(string key,string value){
    (*this)[key] = value;
  }

  string GetValue(string key){
    if (!Contains(key)){
      return(0);
    }else{
      return((*this)[key]);
    }
  }

  void Remove(string key){
    erase(key);
  }

};

//------------------------------------------------------------------------------
// * String2StringMultiMap
//------------------------------------------------------------------------------
// A hash to implement the mapping of a string to multiple strings.
//
class String2StringMultiMap : public  hash_multimap<string,string,
						    BasicStringHashF> {
 public:

  bool Contains(string key){
    pair<String2StringMultiMap::const_iterator,String2StringMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return(false);
    else return(true);
  }
  
  // Returns true if the multimap contains the pair (key,targetvalue)
  bool Contains(string key,string targetvalue){
    pair<String2StringMultiMap::const_iterator,String2StringMultiMap::const_iterator> p;
    p = equal_range(key);
    if (p.first == end()) return(false);

    // The key exists, see if any of this key's values are equal to value..
    String2StringMultiMap::const_iterator it;
    for(it = p.first;it != p.second;it++){
      string value = (*it).second;
      if (value  == targetvalue) return(true);
    }
    return(false);
  }

  
  void Add(string key,vector<string> &Values){
    for(int i = 0;i< Values.size();i++){
      insert(String2StringMultiMap::value_type(key,Values[i]));
    }
  }


  void Add(string key,string Value){
    insert(String2StringMultiMap::value_type(key,Value));
  }
	
  // Walking with an iterator through the multi-map gives you all of the 
  // key-value pairs, but a given key may occurr many times in this list. 
  // This function gives you a non-redundant set of keys. 
  void GetKeys(vector<string> &Keys){
	 
    StringSet S;
    String2StringMultiMap::iterator it;
    for(it = begin();it != end();it++){
      string key = (*it).first;
      S.Add(key);
    }

    StringSet::iterator sit;
    for(sit = S.begin();sit != S.end();sit++){
      Keys.push_back((*sit));
    }
  }

  void GetValues(string key,vector<string> &Values){
    String2StringMultiMap::const_iterator it;
    pair<String2StringMultiMap::const_iterator,String2StringMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return;

    for(it = p.first;it != p.second;it++){
      Values.push_back((*it).second);
    }
  }
 
};



//------------------------------------------------------------------------------
// * Int2StringMap
//------------------------------------------------------------------------------
// A hash to implement the mapping between ints and strings. 
//
//
class  Int2StringMap: public hash_map<int,string,hash<int>,equal_to<int> >{
 public:
  bool Contains(int &query){
    Int2StringMap::iterator it;
    it = (*this).find(query);
    if (it == (*this).end()) return(false);
    else return(true);
  }

  string GetValue(int &key){
    if (!Contains(key)){
      return("");
    }else{
      return((*this)[key]);
    }
  }
  
  void Add(int &key,string &value){
    (*this)[key] = value;
  }
};


//------------------------------------------------------------------------------
// * Int2StringMultiMap
//------------------------------------------------------------------------------
// A hash to implement the mapping of a string to multiple integers. 
//
class Int2StringMultiMap : public  hash_multimap<int,string,hash<int>,equal_to<int> >{
 public:
  bool Contains(int &key){
    Int2StringMultiMap::iterator it;
    pair<Int2StringMultiMap::const_iterator,Int2StringMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return(false);
    else return(true);
  }
  
  void Add(int &key,vector<string> &Values){
    for(int i = 0;i< Values.size();i++){
      insert(Int2StringMultiMap::value_type(key,Values[i]));
    }
  }

  void Add(int &key,string &Value){
    insert(Int2StringMultiMap::value_type(key,Value));
  }

  void GetValues(int &key,vector<string> &Values){
    Int2StringMultiMap::const_iterator it;
    pair<Int2StringMultiMap::const_iterator,Int2StringMultiMap::const_iterator> p;
    p = equal_range(key);
	
    if (p.first == end()) return;

    for(it = p.first;it != p.second;it++){
      Values.push_back((*it).second);
    }
  }
 
};


#endif






